1. Field of the Invention
The present invention relates generally to integrated circuits, and more specifically to a difference flag circuit for use in FIFO memories.
2. Description of the Prior Art
First In First Out (FIFO) memories are used in a variety of applications as an interface between two or more devices which transmit data at different rates of speed. Typical interface applications for FIFOs include placement between a computer and a printer or between a computer and a high speed modem. Because of the speed difference between devices, data stored inside a FIFO may be read out of the FIFO at a different rate than it was written into the FIFO. Since FIFOs are capable of receiving data at a rate different than the rate at which data is read, it is important to quantify the amount of data in the FIFO. Therefore, a FIFO has one or more flags which indicate the data status of the FIFO. Typical FIFO flags indicate full, empty, and half-full data status.
FIFO flag circuitry has historically included comparators and subtractors. The subtractor determines the difference between two values being compared. That difference is then presented as an input to a corresponding comparator. The comparator determines the relationship between two values and whether they are equal or unequal to each other. The appropriate comparator output signal is then generated. The FIFO flag signal is not determined until the subtractors and the comparators have completed their tasks. U.S. Pat. Nos. 4,974,241, issued Nov. 27, 1990 and 4,935,719 issued Jun. 19, 1990 both in the name of inventor David C. McClure, discuss use of serial subtractors and serial comparators to generate FIFO flag logic in the prior art. Traditionally, subtractor circuitry has been slower than comparator circuitry, and so generation of the FIFO flag was impeded as the comparator circuitry waited on the subtractor circuitry. This wait can be quite long in the prior art where serial subtractors and comparators dictated long signal propagation delays. By eliminating the need for subtractors in FIFO flag logic circuitry, the FIFO flag signal may be more quickly generated. U.S. Pat. No. 4,891,788 by inventor Gerard A. Kreifels which issued Jan. 2, 1990 gives insight on prior art techniques for generating FIFO flag logic without the use of a subtractor.
In the prior art, serial magnitude comparators are a common form of comparator circuits. They have a number of individual bit comparators that together serially determine the magnitude of a number relative to another number. First, the least significant bits (LSBs) of the two numbers are compared before comparing the next bits, the LSB+1. This process continues serially until the most significant bits (MSBs) are compared. The serial process can be quite time consuming; at least 16 gate delays will be incurred for comparing two 16 bit words.
The individual bit comparators which comprise a serial magnitude comparator have four inputs: two inputs derived from the two bits to be compared, an input from the compare output of the previous bit comparator, and an input equal to one of the two bits being compared. The compare output of a bit comparator is input to the subsequent bit comparator and reflects whether the magnitude of one bit is equal to, less than, or greater than the magnitude of the second bit. If the two bits being compared are equal, then the compare input is passed through the bit comparator as the compare output. If, however, the two bits are unequal in magnitude, then the input equal to the first bit of the two bits being compared is passed through as the compare output. This comparison process starts with the least significant bit (LSB) comparator and continues until the most significant bit (MSB) comparator finishes its comparison operation. The bit comparator with the highest order bit of difference determines the state of the final compare output.
The gate delays associated with serial magnitude comparators and subtractors can have an adverse effect on generating a FIFO flag signal in a timely manner. Prior art FIFO flag logic, which is dependent on the comparator and subtractor, must be generated quickly. If the magnitude comparator is slow, it will have an adverse affect on how quickly flag logic may be generated and overall FIFO performance will suffer. A fundamental way to enhance the speed at which FIFO flag logic is generated is to minimize propagation and gate delays associated with serial magnitude comparators. It would be desirable to accomplish this using current magnitude comparator design. The speed at which FIFO flag logic is generated may be further enhanced by eliminating the need for subtractor circuitry altogether.